// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-28 18:26
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Tree.TreeArray;

/**
 * 树状数组类
 */
public class TreeArray {
    /**
     * 树状数组类的长度，是指原数组中的元素数量
     * 原数组中的元素需要有序吗？
     */
    int n;
    /**
     * a是原数组，c是树状数组
     */
    int[] a = new int[1005], c = new int[1005];

    /**
     * 方法获取2^k
     */
    int lowbit(int x) {
        return x & (-x);
    }

    void updated(int i, int k) {
        while (i <= n) {
            c[i] += k;
            i += lowbit(i);
        }
    }

    /**
     * 区域求和
     */
    int getSum(int i) {
        int res = 0;
        while (i > 0) {
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
}
